//
//  main.c
//  118. generate(杨辉三角)
//
//  Created by edz on 2020/7/14.
//  Copyright © 2020 edz. All rights reserved.
//

/*
 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
 在杨辉三角中，每个数是它左上方和右上方的数的和。

 示例:
 输入: 5
 输出:
 [
      [1],
     [1,1],
    [1,2,1],
   [1,3,3,1],
  [1,4,6,4,1]
 ]
 */

#include <stdio.h>
#include <stdlib.h>

int** generate(int numRows, int* returnSize, int** returnColumnSizes){
    *returnSize=numRows;
    *returnColumnSizes=(int*)malloc(4*numRows);
    int i,j;
    int**ret=(int**)malloc(sizeof(int*)*numRows);//声明
    for(i=0;i<numRows;++i){
        (*returnColumnSizes)[i]=i+1;//初始化
        ret[i]=(int*)malloc(i*4+4);
        ret[i][0]=1;
        ret[i][i]=1;
    }
    for(i=2;i<numRows;++i)
        for(j=1;j<i;++j)
            ret[i][j]=ret[i-1][j-1]+ret[i-1][j];//计算
    return ret;
}


// java实现
/*
class Solution {
    public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> triangle = new ArrayList<List<Integer>>();
    if (numRows == 0) {
        return triangle;
    }
    
    triangle.add(new ArrayList<>());
    triangle.get(0).add(1);
    
    for (int rowNum = 1; rowNum < numRows; rowNum++) {
        List<Integer> row = new ArrayList<>();
        List<Integer> prevRow = triangle.get(rowNum-1);
        
        row.add(1);
        for (int j = 1; j < rowNum; j++){
            row.add(prevRow.get(j-1) + prevRow.get(j));
        }
        row.add(1);
        triangle.add(row);
    }
    return triangle;
    }
}
*/
